package leetcode.datastructure.array;

import java.util.Arrays;

/**
 * 乘法太多浪费计算时间
 */
public class Program45JumpGame {

    public Program45JumpGame() {
    }

    public int jump(int[] nums) {
//        return dpArray(nums);
        return dpSingle(nums);
    }

    public int dpSingle(int[] nums) {
        int cover = 0;
        int count = 0;
        int cur = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            cover = Math.max(cover,i + nums[i]);
            // 每一轮定位的最大值
            if (cur == i) {
                count++;
                cur = cover;
            }
        }
        return count;
    }
    public int dpArray(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return 0;
        }
        int[] dp = new int[length];
        Arrays.fill(dp, length);
        dp[0] = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i; j <= Math.min(i + nums[i], length - 1);j++) {
                dp[j] = Math.min(dp[i] + 1, dp[j]);
            }
        }
        return dp[length - 1];
    }

    public static void main(String[] args) {
        Program45JumpGame myStack = new Program45JumpGame();
        int[] prices = {2,3,0,1,4};
        System.out.println(myStack.jump(prices));
        int[] prices2 = {2,3,1,1,4};
        System.out.println(myStack.jump(prices2));
        int[] prices3 = {2,0,0};
        System.out.println(myStack.jump(prices3));
    }
}
